In the field of telecommunications, there is great interest in iterative decoding algorithms. Some error correcting codes, such as turbo-codes and low-density parity-check (LDPC) codes require iterative decoding to properly determine the encoded message after transmission through a noisy channel. Attention is directed to iterative decoding methods due to their contribution to the overall coded channel performance.
After their introduction by Gallager in the 1960's, LDPC codes were considered to be too computationally complex to be easily implemented. However, as computational power of telecommunications equipment advanced, and in concert with the interest paid to turbo-codes, LDPC codes have been an area of great focus and development.
The iterative decoding of turbo and LDPC codes is an area of particular interest in the field. Improvements in decoding techniques have allowed greater utilization of telecommunication channels.
For the sake of clarity, the following discussion will focus on the iterative decoding of LDPC codes, through one skilled in the art will appreciate that similar approaches are employed in other iterative decoding approaches.
A graphical representation of an iterative decoder 100 known in the art is provided in FIG. 1. A plurality of variable-nodes, labelled v1 102, v2 104, v3 106, v4 108, v5 110, and v6 112, receive a sequence of samples representing a series of symbols, forming a code word, transmitted by an encoder. Due to the presence of noise in the transmission channel, the sequence of samples cannot be simply mapped to a series of symbols using a look up table. However, with sufficient use of error-correction coding, a received sequence of samples can be decoded to a candidate codeword with a desired amount of certainty. Each variable-node is connected to at least one of the check-nodes labelled c1 114, c2 116, c3 118 and c4 120. Each connection between a variable-node and a check-node is referred to as an edge. Along these edges, messages are passed between the nodes. Each node, either check or variable, applies a predefined function to the received message prior to passing the result back.
The functions performed by the variable and check-nodes correspond to a desired decoding algorithm such as majority-based (MB) algorithms, minimum sum (min-sum) algorithms and belief propagation algorithms. MB algorithms can be implemented with minimal computational complexity, and a small implementation area, as they rely upon hard decisions. Min-sum and belief propagation algorithms provide faster convergence than MB algorithms, which can be used to reduce the number of iterations required to obtain the desired certainty in decoding, however, both these algorithm types rely upon soft decisions, and are thus more computationally complex, and require a greater implementation area for the increased logic required. The more computationally complex algorithms also allow reliable communication to be achieved over channels with worse characteristics than the worst channel that MB algorithms can reliably work over.
In conventional iterative decoding systems, such as the one illustrated in FIG. 1, decoder 100 will iteratively decode the received sequence of samples using a selected algorithm by repeatedly passing extrinsic messages between the variable and check-nodes. The algorithm used by the nodes is selected based on an acceptable trade-off in the number of iterations required, the time required by each iteration, and the implementation complexity. The implemented algorithm is preferably selected and implemented with knowledge about the characteristics of the transmission channel and the encoding method. The arrangement of the edges is specifically related to the encoding methodology, and allows for the decoding of encoded messages. The selection of the decoding algorithm based on knowledge of the transmission channel allows algorithms to be refined to improve their decoding performance based on specific channel properties such as noise distribution.
Although soft decision algorithms provide improved performance, they impose implementation complexity penalties related to the time required to execute each iteration and to the required implementation area. Decoders implemented solely in software are concerned largely with the first of the penalties, while dedicated hardware decoders are more concerned with the second of the penalties. In a hardware decoder, the increased logic required to implemented soft decoding algorithms also imposes a power consumption penalty, which often serves as an incentive to use hard decision algorithms such as MB algorithms despite the longer convergence time.
In the 1960's Gallager offered a hybridized decoder architecture that offers some of the performance advantages of soft decision decoding while reducing the computational complexity required by conventional soft decision decoders. The decoder taught by Gallager is a type of a hybrid switch type (HST) decoder. If a decoding operation can be represented by a function Δ, the hybrid switch type decoding operation is represented by a function Δ(l), where l represents the iteration number. The simplest of the hybrid switch type decoders is represented by the function
      Δ    ⁡          (      l      )        =      {                                                                      Δ                A                            ,                              0                ≤                l                ≤                x                                                                                                        Δ                B                            ,                              x                <                l                                                        .      
Graphically represented, the decoder is identical to the decoder illustrated in FIG. 1 for 0≦l≦x. However, after the xth iteration, a new set of operators are performed by the check and variable-nodes to perform the decoding operation. This allows a switch between decoding algorithms. After the xth iteration, the hybrid switch type decoder is represented by decoder 122 of FIG. 2. Variable-node v1B 124, v2B 126, v3B 128, v4B 130, 132 and v6B 134 connect to the check-nodes c1B 136, c2B 138, c3B 140 and c4B 142, same configuration as the decoder of FIG. 1, however, both the check and the variable-nodes perform different operations that correspond to the new decoding function ΔB. Along with the new operators, the style of message passed along the edges can also change at the switch point.
The HST architecture decoders allow for a fixed number of iterations to be performed using a more complex decoding algorithm, while allowing the bulk of the iterations to be performed with simple to implement decoding algorithms such as MB algorithms. Even a few iterations using a more robust operation, such as min-sum, greatly reduces the performance gap between the robust and the computationally simple implementations, while also reducing the overall computational intensity of the decoding operation. It has also been found the even if only MB algorithms are used, HST implementations provide performance improvements over the constituent codes. One great detriment to the implementation of hardware based HST decoders is the increased implementation area required. Because the variable and check-nodes for each iteration grouping perform different operations, different sets of variable and check-nodes must be provided, as does message routing circuitry for managing the switchover between operations. FIG. 3 illustrates an exemplary logical implementation of an HST decoder for
      Δ    ⁡          (      l      )        =      {                                                                      Δ                A                            ,                              0                ≤                l                ≤                x                                                                                                        Δ                B                            ,                              x                <                l                                                        .      As illustrated in FIG. 3, the implementation of an HST decoder 144 requires the connection of decoder 100 to decoder 122. The overall structure includes the variable and check-nodes corresponding to function ΔA, v1A 102, v2A 104, v3A 106, v4A 108, v5A 110, v6A 112, c1A 114, c2A 116, c3A 118 and c4A 120 arranged as they are in FIG. 1. However, the check-nodes, c1A 114, c2A 116, c3A 118 and c4A 120, have an external control so that after a predetermined number of iterations, in this example after the xth iteration, the check-nodes pass the message to the variable-nodes corresponding to the second decoding function ΔB, v1B 124, v2B 126, v3B 128, v4B 130, v5B 132 and v6B 134. The second set of variable-nodes iteratively pass messages to the second set of check-nodes c1B 136, c2B 138, c3B 140 and c4B 142, with the same edge configuration. The connection of the first set of check-nodes to the second set of variable-nodes uses the same edge mapping as the first stage. One skilled in the art will appreciate that if the function performed by the first and second set of check-nodes is the same, the second set of check-nodes could be omitted, and the messages would be passed along the edges between the check-node and each of the two sets of variable-nodes as determined by the routing control. In another embodiment, if the variable-nodes perform the same operation, but the check-nodes perform a different operation after the switch, the variable-nodes can be reused.
The implementation of FIG. 3 illustrates one of the great disadvantages of the hardware implementation of an HST decoder. Because the variable-nodes and check-nodes perform different operations, each function used in an HST decoder must have its own set of variable-nodes. Thus, the performance benefit of the HST decoder is offset by an implementation complexity penalty. Re-use of circuitry between the two different sets of variable-nodes is difficult as the logic used for different operators does not typically provide a great deal of overlap. Furthermore, soft decision operators heavily rely upon a characterization of the transmission channel, and repeated iterations using soft decision operators relying upon an erroneous characterization are known to decrease the performance of a decoder.
Codes can be classified as either regular or irregular based on their graphical representations. In a regular code, each variable-node connects to the same number of check-nodes as every other variable-node, and similarly every check-node connects to the same number of variable-nodes as every other check-node. Thus a code described as a regular (dv, dc) code has every variable-node connected to dv check-nodes, and every check-node connected to dc variable-nodes. In such a code, the variable-nodes are referred to as being of degree dv as they each have dv edges. In an irregular code, nodes can be grouped by their degree, so that one grouping of variable-nodes are of degree dv1, while another grouping are of degree dv2. Thus the variable-nodes in the first grouping connect to dv1 check-nodes, while the variable-nodes in the second grouping connect to dv2 check-nodes. Check-nodes can be similarly partitioned.
In an irregular HST decoder, each node in a degree grouping switches to the next constituent algorithm with the other nodes in its group, but not necessarily with the all other nodes of its type. As a result, an HST decoder having 20% of its variable-nodes of degree dv1, and 80% of its variable-nodes of degree dv2, switching between MB algorithms can have all variable-nodes start with MB0, after the 10th iteration have all variable-nodes of degree dv1 switch to MB1, after the 15th iteration have all variable-nodes of degree dv2 switch to MB2, and after the 20th iteration have all variable-nodes of degree dv1 also switch to MB2. Irregular HST decoders provide performance improvements over regular HST decoders with proper selection of the degree groupings, the constituent algorithms assigned to the groupings and the iteration at which algorithms are switched. In each of the MB algorithms, the check-nodes perform the same operation, so switching between consistent algorithms in the check-nodes is not necessary. The irregularity described above relates to an irregular edge structure.
From the above discussion it is apparent to one skilled in the art, that standard iterative decoders either lack sufficient performance and require too many iterations to converge, or rely upon complex circuitry and channel characterizations that must be accurate, while HST decoders are difficult to implement in hardware, and regardless of how they are implemented are heavily reliant upon the correct characterization of the transmission channel to obtain desired performance. Though channel characterization is possible, it is often found that the laboratory characterization of channel does not identically correspond to real world situations, where installation of a physical channel can introduce irregularities in the channel properties, as does the aging of an installed channel. Non-installed channels, such as wireless communications links, are also subject to unplanned changes in their characteristics over finite time intervals, which adversely affect the performance of functions dependent upon accurate channel characterization.
It is, therefore, desirable to provide an iterative decoder architecture that simplifies implementation in hardware, and offers a reasonable degree of immunity to variation in the characterization of a channel.